{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "google",
   "metadata": {},
   "source": [
    "##### Copyright 2023 Google LLC."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "apache",
   "metadata": {},
   "source": [
    "Licensed under the Apache License, Version 2.0 (the \"License\");\n",
    "you may not use this file except in compliance with the License.\n",
    "You may obtain a copy of the License at\n",
    "\n",
    "    http://www.apache.org/licenses/LICENSE-2.0\n",
    "\n",
    "Unless required by applicable law or agreed to in writing, software\n",
    "distributed under the License is distributed on an \"AS IS\" BASIS,\n",
    "WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\n",
    "See the License for the specific language governing permissions and\n",
    "limitations under the License.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "basename",
   "metadata": {},
   "source": [
    "# coloring_ip"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "link",
   "metadata": {},
   "source": [
    "<table align=\"left\">\n",
    "<td>\n",
    "<a href=\"https://colab.research.google.com/github/google/or-tools/blob/main/examples/notebook/contrib/coloring_ip.ipynb\"><img src=\"https://raw.githubusercontent.com/google/or-tools/main/tools/colab_32px.png\"/>Run in Google Colab</a>\n",
    "</td>\n",
    "<td>\n",
    "<a href=\"https://github.com/google/or-tools/blob/main/examples/contrib/coloring_ip.py\"><img src=\"https://raw.githubusercontent.com/google/or-tools/main/tools/github_32px.png\"/>View source on GitHub</a>\n",
    "</td>\n",
    "</table>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "doc",
   "metadata": {},
   "source": [
    "First, you must install [ortools](https://pypi.org/project/ortools/) package in this colab."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "install",
   "metadata": {},
   "outputs": [],
   "source": [
    "%pip install ortools"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "description",
   "metadata": {},
   "source": [
    "\n",
    "\n",
    "  Simple coloring problem using MIP in Google CP Solver.\n",
    "\n",
    "  Inspired by the GLPK:s model color.mod\n",
    "  '''\n",
    "  COLOR, Graph Coloring Problem\n",
    "\n",
    "  Written in GNU MathProg by Andrew Makhorin <mao@mai2.rcnet.ru>\n",
    "\n",
    "  Given an undirected loopless graph G = (V, E), where V is a set of\n",
    "  nodes, E <= V x V is a set of arcs, the Graph Coloring Problem is to\n",
    "  find a mapping (coloring) F: V -> C, where C = {1, 2, ... } is a set\n",
    "  of colors whose cardinality is as small as possible, such that\n",
    "  F(i) != F(j) for every arc (i,j) in E, that is adjacent nodes must\n",
    "  be assigned different colors.\n",
    "  '''\n",
    "\n",
    "  Compare with the MiniZinc model:\n",
    "    http://www.hakank.org/minizinc/coloring_ip.mzn\n",
    "\n",
    "  This model was created by Hakan Kjellerstrand (hakank@gmail.com)\n",
    "  Also see my other Google CP Solver models:\n",
    "  http://www.hakank.org/google_or_tools/\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "code",
   "metadata": {},
   "outputs": [],
   "source": [
    "import sys\n",
    "from ortools.linear_solver import pywraplp\n",
    "\n",
    "\n",
    "def main(sol='CBC'):\n",
    "\n",
    "  # Create the solver.\n",
    "  print('Solver: ', sol)\n",
    "  solver = pywraplp.Solver.CreateSolver(sol)\n",
    "  if not solver:\n",
    "    return\n",
    "\n",
    "  #\n",
    "  # data\n",
    "  #\n",
    "\n",
    "  # max number of colors\n",
    "  # [we know that 4 suffices for normal maps]\n",
    "  nc = 5\n",
    "\n",
    "  # number of nodes\n",
    "  n = 11\n",
    "  # set of nodes\n",
    "  V = list(range(n))\n",
    "\n",
    "  num_edges = 20\n",
    "\n",
    "  #\n",
    "  # Neighbours\n",
    "  #\n",
    "  # This data correspond to the instance myciel3.col from:\n",
    "  # http://mat.gsia.cmu.edu/COLOR/instances.html\n",
    "  #\n",
    "  # Note: 1-based (adjusted below)\n",
    "  E = [[1, 2], [1, 4], [1, 7], [1, 9], [2, 3], [2, 6], [2, 8], [3, 5], [3, 7],\n",
    "       [3, 10], [4, 5], [4, 6], [4, 10], [5, 8], [5, 9], [6, 11], [7, 11],\n",
    "       [8, 11], [9, 11], [10, 11]]\n",
    "\n",
    "  #\n",
    "  # declare variables\n",
    "  #\n",
    "\n",
    "  # x[i,c] = 1 means that node i is assigned color c\n",
    "  x = {}\n",
    "  for v in V:\n",
    "    for j in range(nc):\n",
    "      x[v, j] = solver.IntVar(0, 1, 'v[%i,%i]' % (v, j))\n",
    "\n",
    "  # u[c] = 1 means that color c is used, i.e. assigned to some node\n",
    "  u = [solver.IntVar(0, 1, 'u[%i]' % i) for i in range(nc)]\n",
    "\n",
    "  # number of colors used, to minimize\n",
    "  obj = solver.Sum(u)\n",
    "\n",
    "  #\n",
    "  # constraints\n",
    "  #\n",
    "\n",
    "  # each node must be assigned exactly one color\n",
    "  for i in V:\n",
    "    solver.Add(solver.Sum([x[i, c] for c in range(nc)]) == 1)\n",
    "\n",
    "  # adjacent nodes cannot be assigned the same color\n",
    "  # (and adjust to 0-based)\n",
    "  for i in range(num_edges):\n",
    "    for c in range(nc):\n",
    "      solver.Add(x[E[i][0] - 1, c] + x[E[i][1] - 1, c] <= u[c])\n",
    "\n",
    "  # objective\n",
    "  objective = solver.Minimize(obj)\n",
    "\n",
    "  #\n",
    "  # solution\n",
    "  #\n",
    "  solver.Solve()\n",
    "\n",
    "  print()\n",
    "  print('number of colors:', int(solver.Objective().Value()))\n",
    "  print('colors used:', [int(u[i].SolutionValue()) for i in range(nc)])\n",
    "  print()\n",
    "\n",
    "  for v in V:\n",
    "    print('v%i' % v, ' color ', end=' ')\n",
    "    for c in range(nc):\n",
    "      if int(x[v, c].SolutionValue()) == 1:\n",
    "        print(c)\n",
    "\n",
    "  print()\n",
    "  print('WallTime:', solver.WallTime())\n",
    "  if sol == 'CBC':\n",
    "    print('iterations:', solver.Iterations())\n",
    "\n",
    "\n",
    "\n",
    "sol = 'CBC'\n",
    "if len(sys.argv) > 1:\n",
    "  sol = sys.argv[1]\n",
    "  if sol != 'GLPK' and sol != 'CBC':\n",
    "    print('Solver must be either GLPK or CBC')\n",
    "    sys.exit(1)\n",
    "\n",
    "main(sol)\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 5
}
